package com.atcumt.Write.sort;

import java.util.*;

/**
 * 拓扑排序
 * 1、得到一个拓扑序
 * 2、检测有向图是否有环 (无向图是否有环使用的是并查集)
 */
public class KahnSort {

    /*
    课程表
    1、根据依赖关系，构建邻接表、入度数组。
    2、选取入度为 0 的数据，根据邻接表，减小依赖它的数据的入度。
    3、找出入度变为 0 的数据，重复第 2 步。
    4、直至所有数据的入度为 0 或者count = numCourses得到排序，否则说明图中存在环
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses <= 0) {
            return false;
        }
        if (prerequisites == null || prerequisites.length == 0) {
            return true;
        }

        int[] inDegree = new int[numCourses]; // 入度数组
        HashMap<Integer, List<Integer>> adj = new HashMap<>();

        // 初始化入度和邻接表
        for (int[] relate : prerequisites){
            inDegree[relate[0]]++; // 统计入度
            // 邻接表赋值
            if (!adj.containsKey(relate[1])) {
                adj.put(relate[1], new ArrayList<>());
            }
            adj.get(relate[1]).add(relate[0]);
        }

        // BFS
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }
        // 取出一个节点, 对应学习这门课程.
        // 遍历当前邻接表, 更新其入度; 更新之后查看入度, 如果为0, 加入到队列
        int count = 0;
        while (!queue.isEmpty()) {
            count++;
            int cur = queue.poll();
            if (!adj.containsKey(cur)) {
                continue;
            }
            List<Integer> successList = adj.get(cur);
            for (int i : successList) {
                inDegree[i]--;
                if (inDegree[i] == 0) {
                    queue.add(i);
                }
            }
        }
        return count == numCourses;
    }
}
